import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 20404
 * Date: 2023-01-28
 * Time: 13:19
 */




public class MyLinkedList{
    private int size;

    Node head;
    Node last;

    @Override
    public String toString() {
        return "MyLinkedList{" +
                " " + size +
                ", " + head +
                '}';
    }
    public MyLinkedList() {

    }


    public static class Node{
        private int value;
        Node next;
        Node prev;

        @Override
        public String toString() {
            return "{" +
                    " " + value +
                    ", " + next +
                    '}';
        }

        public Node(int value) {
            this.value = value;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }
    }
    public void addFirst(int data) {
        size++;
        Node newOne = new Node(data);
        if(head == null) {
            last = newOne;
            head = newOne;
        }else {
            newOne.next = head;
            head.prev = newOne;
            head = newOne;
        }
    }

    public void display() {
        Node cur = head;
        System.out.print("[ ");
        while(cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }System.out.println("]");
    }
    public static void display(Node head) {
        Node cur = head;
        System.out.print("[ ");
        while(cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }System.out.println("]");
    }
    public void addLast(int data) {
        size++;
        Node newOne = new Node(data);
        if(last == null) {
            head = newOne;
            last = newOne;
        }else {
            newOne.prev = last;
            last.next = newOne;
            last = newOne;
        }
    }
    public void addIndex(int index,int data) {
        try {
            checkIndex(index, "Exception from addIndex(...)");
        } catch (IndexOutOfException e) {
            e.printStackTrace();
            return;
        }
        Node cur = head;
        Node newOne = new Node(data);
        if(index == 0) {
            addFirst(data);
        }else if(index == size) {
            addLast(data);
        }else {
            while(index-- != 0) { // --index 是因为那个单链表找不到前一个节点
                cur = cur.next;
            }
            newOne.next = cur;
            newOne.prev = cur.prev;
            cur.prev.next = newOne;
            cur.prev = newOne;
            size++;
        }
    }

    private void checkIndex(int index, String str) {
        if(index < 0 || index > size) {
            throw new IndexOutOfException(str);
        }
    }
    public Node getNode(int index) {
        try {
            checkIndex(index, "Exception from getNode(...)");
            Node cur = head;
            while(index-- != 0) {
                cur = cur.next;
            }
            return cur;
        } catch (IndexOutOfException e) {
            e.printStackTrace();
            return null;
        }
    }

    private Node searchPreviousOne(int index) {
        try {
            checkIndex(index, "Exception from searchPreviousOne(...)");
        } catch (IndexOutOfException e) {
            e.printStackTrace();
            return null;
        }
        if(index == 0) {
            return null;
        }
        Node cur = head;
        while(--index != 0) {
            cur = cur.next;
        }
        return cur;
    }
    private Node searchPreviousOne(Integer val) {
        int value = val.intValue();
        if (value == head.value || !contains(value)) {
            return null;
        } else {
            Node cur = head;
            while (cur.next != null) {
                if (cur.next.value == value) {
                    return cur;
                } else {
                    cur = cur.next;
                }
            }
        }
        return null;
    }
    public boolean contains(int key) {
        if(head != null) {
            Node cur = head;
            while(cur != null) {
                if(cur.value == key) {
                    return true;
                }else {
                    cur = cur.next;
                }
            }
        }
        return false;
    }
    public void remove(int key) {
        Node cur = head;
        while(cur != null) {
            if(cur.value == key) {
                if(cur == head) {
                    cur.next.prev = null;
                    head = head.next;
                }else if (cur == last) {
                    cur.prev.next = null;
                    last = last.prev;
                }else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
                size--;
                return;
            }
            cur = cur.next;
        }
    }
    public void removeAllKey(int key) {
        Node cur = head;
        while(cur != null) {
            if(cur.value == key) {
                if(cur == head) {
                    cur.next.prev = null;
                    head = head.next;
                }else if (cur == last) {
                    cur.prev.next = null;
                    last = last.prev;
                }else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
                size--;
            }
            cur = cur.next;
        }
    }
    public int size() {
        return this.size;
    }

    public void clear() {
        size = 0;
        while(head != null) {
            head = head.next;
            if(head == null) {
                last = null;
                return;
            }
            head.prev = null;
        }
    }


    public static Node addTwoNumbers(Node l1, Node l2) {
        long numb1 = 0;
        long numb2 = 0;
        long flag = 1;
        while(l1 != null && l2 != null) {
            numb1 += flag * l1.value;
            numb2 += flag * l2.value;
            flag *= 10;
            l1 = l1.next;
            l2 = l2.next;
        }
        while(l1 != null) {
            numb1 += flag * l1.value;
            l1 = l1.next;
            flag *= 10;
        }
        while(l2 != null) {
            numb2 += flag * l2.value;
            l2 = l2.next;
            flag *= 10;
        }
        long numb = numb1 + numb2;
        if(numb == 0) {
            return new Node(0);
        }
        Node ret = null;
        Node last = null;
        while(numb != 0) {
            long n = numb % 10;
            numb /= 10;
            Node newOne = new Node((int)n);
            if(last == null) {
                ret = newOne;
                last = newOne;
            }else {
                last.next = newOne;
                last = last.next;
            }
        }
        return ret;
    }
    public Node addTwoNumbers2(Node l1, Node l2) {
        int change = 0;
        Node ret = null;
        Node last = null;
        while(l1 != null && l2 != null) {
            int flag = change + l1.value + l2.value;
            change = flag / 10;
            Node newOne = new Node(flag % 10);
            if(last == null) {
                ret = newOne;
                last = newOne;
            }else {
                last.next = newOne;
                last = last.next;
            }
            l1 = l1.next;
            l2 = l2.next;
        }
        return ret;
    }
    public static Node sortList(Node head) {
        int count = 0;
        if(head == null) {
            return null;
        }
        Node ret = head;
        Node prevHead = null;
        while(head != null) {
            Node maxNode = head;
            Node cur = head;
            Node prev = head;
            while(cur != null) {
                if(cur.next != null && cur.next.value > maxNode.value) {
                    prev = cur;
                    maxNode = cur.next;
                }
                cur = cur.next;
            }
            if(count == 0) {
                prevHead = maxNode;
                count++;
            }
            if(maxNode == ret) {
                head = head.next;
                continue;
            }
            if(maxNode == head) {
                prev = prevHead;
                head = head.next;
            }
            Node linker = maxNode;
            prev.next = maxNode.next;
            linker.next = ret;
            ret = linker;
        }
        List<Integer> list = new ArrayList<>();
        return ret;
    }
}

